{
 "cells": [
  {
   "cell_type": "code",
   "id": "c2ad8cc2-2daa-425a-b11b-851b0a52bd54",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-08-15T07:22:25.414850Z",
     "start_time": "2025-08-15T07:22:25.366374Z"
    }
   },
   "source": [
    "import numpy as np     #只需要下载numpy库即可\n",
    "import random\n",
    "import GridWorld_v1"
   ],
   "outputs": [],
   "execution_count": 1
  },
  {
   "cell_type": "code",
   "id": "441bf83e-6a37-45f1-829e-b1affd2194b0",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-08-15T07:22:25.418980Z",
     "start_time": "2025-08-15T07:22:25.415853Z"
    }
   },
   "source": [
    "gamma = 0.9   #折扣因子，越接近0越近视\n",
    "rows = 5      #记得行数和列数这里要同步改\n",
    "columns = 5\n",
    "# gridworld = GridWorld_v1.GridWorld_v1(rows=rows, columns=columns, forbiddenAreaNums=4, targetNums=2, seed = random.randint(1,1000))\n",
    "# gridworld = GridWorld_v1.GridWorld_v1(desc = [\".#\",\".T\"])             #赵老师4-1的例子\n",
    "# gridworld = GridWorld_v1.GridWorld_v1(desc = [\"##.T\",\"...#\",\"....\"])  #随便弄的例子\n",
    "gridworld = GridWorld_v1.GridWorld_v1(forbiddenAreaScore=-10, score=1,desc = [\".....\",\".##..\",\"..#..\",\".#T#.\",\".#...\"]) \n",
    "gridworld.show()\n",
    "\n",
    "\n",
    "value = np.zeros(rows*columns)       #初始化可以任意，也可以全0，这是state-value\n",
    "qtable = np.zeros((rows*columns,5))  #初始化，这里主要是初始化维数，里面的内容会被覆盖所以无所谓,这里的5是action的数量,这里的qtable就是Q表格,这里是action-value\n",
    "policy = np.argmax(qtable,axis=1)    #初始策略\n",
    "gridworld.showPolicy(policy)"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "⬜️⬜️⬜️⬜️⬜️\n",
      "⬜️🚫🚫⬜️⬜️\n",
      "⬜️⬜️🚫⬜️⬜️\n",
      "⬜️🚫✅🚫⬜️\n",
      "⬜️🚫⬜️⬜️⬜️\n",
      "⬆️⬆️⬆️⬆️⬆️\n",
      "⬆️⏫️⏫️⬆️⬆️\n",
      "⬆️⬆️⏫️⬆️⬆️\n",
      "⬆️⏫️✅⏫️⬆️\n",
      "⬆️⏫️⬆️⬆️⬆️\n"
     ]
    }
   ],
   "execution_count": 2
  },
  {
   "cell_type": "code",
   "id": "d4ca8229-dbdb-4566-9bc8-20ee11bdd104",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-08-15T07:22:25.429850Z",
     "start_time": "2025-08-15T07:22:25.418980Z"
    }
   },
   "source": [
    "policy = np.random.randint(0,5,size=(rows*columns)) \n",
    "#随机[0,5)的整数，代表策略\n",
    "#这里其实不严谨，因为策略是可以不百分百选一个方向的，可以0.5向上，0.5向右，诸如此类。\n",
    "#但先不考虑那种情况，因为画图不好画，代码实现逻辑是没差多少的"
   ],
   "outputs": [],
   "execution_count": 3
  },
  {
   "cell_type": "code",
   "id": "e194fb9d-b915-4a9f-b129-6a1a35f53376",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-08-15T07:22:25.433854Z",
     "start_time": "2025-08-15T07:22:25.430855Z"
    }
   },
   "source": [
    "gridworld.showPolicy(policy)"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "⬆️⬇️⬆️⬅️⬇️\n",
      "⬅️⏫️⏬🔄➡️\n",
      "⬅️🔄🔄⬅️⬅️\n",
      "⬇️🔄✅🔄➡️\n",
      "⬅️⏪⬆️🔄⬅️\n"
     ]
    }
   ],
   "execution_count": 4
  },
  {
   "cell_type": "code",
   "id": "87a7520b-d085-40f3-a6ac-154055ffa221",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-08-15T07:22:25.445280Z",
     "start_time": "2025-08-15T07:22:25.435056Z"
    }
   },
   "source": [
    "#求解贝尔曼方程\n",
    "gridworld.show()                     #打印gridworld\n",
    "gridworld.showPolicy(policy)         #打印策略\n",
    "print(\"random policy\")\n",
    "#policy evaluation\n",
    "value = np.zeros(rows*columns)\n",
    "value_pre = value.copy()+1\n",
    "\n",
    "cnt = 0\n",
    "while(np.sum((value_pre-value)**2)>0.001):\n",
    "    #policy evaluation\n",
    "    \n",
    "    value_pre = value.copy() #用来验证整个迭代是否收敛的\n",
    "\n",
    "    value0 = value.copy()+1  #这里是随机一个值，然后通过迭代的方式求解贝尔曼方程\n",
    "                             #这里写了固定，也可以随机，最终都会收敛到同一个结果\n",
    "    \n",
    "    truncatedCnt = 10       # 1:迭代50次  2：迭代26次 3：迭代18次 4：迭代14次  10：迭代6次 100：迭代2次\n",
    "    while(np.sum((value0-value)**2)>0.001):\n",
    "        value0 = value.copy()\n",
    "        \n",
    "        truncatedCnt = truncatedCnt-1  #这里加个限制，其实就是truncated policy iteration了\n",
    "        if truncatedCnt<0:             #如果没有这里，其实就是贝尔曼迭代次数\n",
    "            break\n",
    "                \n",
    "        for i in range(rows * columns):   #使用当前策略policy，计算每个state的value，进行迭代\n",
    "            j = policy[i]                 #不用遍历5个action了，直接百分百选择policy的策略\n",
    "            score, nextState = gridworld.getScore(i,j)   #返回得分以及下一步的state id\n",
    "            value[i] = score + value0[nextState] * gamma #贝尔曼迭代\n",
    "    \n",
    "    #policy improvement\n",
    "    for i in range(rows * columns):\n",
    "        for j in range(5): # 5个action\n",
    "            score,nextState = gridworld.getScore(i,j)        #获取Si状态中，执行动作j后的（得分，下一个状态）\n",
    "            qtable[i][j] = score + gamma * value[nextState]  #开始迭代，更新qtable，这样才能知道哪个策略最好，谁的action-value大,对应的策略就会被选择\n",
    "\n",
    "    #policy improvement,和伪代码对应\n",
    "    policy = np.argmax(qtable,axis=1)  #更新策略，非常无敌\n",
    "\n",
    "\n",
    "    \n",
    "    gridworld.showPolicy(policy)      #各种打印信息\n",
    "    print(np.round(value.reshape(rows,columns), 1))\n",
    "    cnt = cnt+1\n",
    "    print(cnt)\n",
    "\n",
    "    "
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "⬜️⬜️⬜️⬜️⬜️\n",
      "⬜️🚫🚫⬜️⬜️\n",
      "⬜️⬜️🚫⬜️⬜️\n",
      "⬜️🚫✅🚫⬜️\n",
      "⬜️🚫⬜️⬜️⬜️\n",
      "⬆️⬇️⬆️⬅️⬇️\n",
      "⬅️⏫️⏬🔄➡️\n",
      "⬅️🔄🔄⬅️⬅️\n",
      "⬇️🔄✅🔄➡️\n",
      "⬅️⏪⬆️🔄⬅️\n",
      "random policy\n",
      "⬇️➡️➡️⬇️⬅️\n",
      "⬆️⏬⏩️🔄⬅️\n",
      "➡️🔄⏪⬆️⬆️\n",
      "🔄⏫️✅⏬⬇️\n",
      "⬆️⏪➡️➡️⬅️\n",
      "[[ -6.5 -34.3  -6.5  -5.5  -5.5]\n",
      " [ -6.5 -30.9 -65.1   0.   -6.5]\n",
      " [ -6.5   0.  -65.1 -65.1 -55.1]\n",
      " [ -5.5 -65.1 -65.1 -65.1  -6.5]\n",
      " [ -6.5  -5.5 -54.1   0.    0. ]]\n",
      "1\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬇️⏫️⏫️⬆️⬆️\n",
      "➡️⬅️⏬⬆️⬆️\n",
      "⬆️⏩️✅⏪⬆️\n",
      "⬆️⏩️⬆️➡️⬆️\n",
      "[[-2.3  0.   0.   0.   0. ]\n",
      " [-2.3  0.   0.   0.   0. ]\n",
      " [ 0.   0.   0.   0.   0. ]\n",
      " [-1.9  0.   0.   0.   0. ]\n",
      " [-1.9 -1.9  0.   0.   0. ]]\n",
      "2\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏫️⬆️⬆️\n",
      "⬆️⬅️⏬⬆️⬆️\n",
      "⬆️⏩️✅⏪⬆️\n",
      "⬆️⏩️⬆️⬅️⬆️\n",
      "[[0.  0.  0.  0.  0. ]\n",
      " [0.  0.  0.  0.  0. ]\n",
      " [0.  0.  6.5 0.  0. ]\n",
      " [0.  6.5 6.5 6.5 0. ]\n",
      " [0.  5.5 6.5 0.  0. ]]\n",
      "3\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏫️⬆️⬆️\n",
      "⬆️⬅️⏬⬆️⬆️\n",
      "⬆️⏩️✅⏪⬆️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[0.  0.  0.  0.  0. ]\n",
      " [0.  0.  0.  0.  0. ]\n",
      " [0.  0.  8.8 0.  0. ]\n",
      " [0.  8.8 8.8 8.8 0. ]\n",
      " [0.  7.8 8.8 7.8 0. ]]\n",
      "4\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏫️⬆️⬆️\n",
      "⬆️⬅️⏬⬆️⬆️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[0.  0.  0.  0.  0. ]\n",
      " [0.  0.  0.  0.  0. ]\n",
      " [0.  0.  9.6 0.  0. ]\n",
      " [0.  9.6 9.6 9.6 0. ]\n",
      " [0.  8.6 9.6 8.6 7.7]]\n",
      "5\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏫️⬆️⬆️\n",
      "⬆️⬅️⏬⬆️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[0.  0.  0.  0.  0. ]\n",
      " [0.  0.  0.  0.  0. ]\n",
      " [0.  0.  9.9 0.  0. ]\n",
      " [0.  9.9 9.9 9.9 7.1]\n",
      " [0.  8.9 9.9 8.9 8. ]]\n",
      "6\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏫️⬆️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[0.  0.  0.  0.  0. ]\n",
      " [0.  0.  0.  0.  0. ]\n",
      " [0.  0.  9.9 0.  6.5]\n",
      " [0.  9.9 9.9 9.9 7.2]\n",
      " [0.  8.9 9.9 8.9 8. ]]\n",
      "7\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏫️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[ 3.5  3.8  4.3  4.8  5.3]\n",
      " [ 3.1  3.5  3.8  4.3  5.9]\n",
      " [ 2.8  2.5 10.   5.9  6.5]\n",
      " [ 2.5 10.  10.  10.   7.3]\n",
      " [ 2.3  9.  10.   9.   8.1]]\n",
      "8\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[ 3.5  3.8  4.3  4.8  5.3]\n",
      " [ 3.1  3.5  3.8  5.3  5.9]\n",
      " [ 2.8  2.5 10.   5.9  6.5]\n",
      " [ 2.5 10.  10.  10.   7.3]\n",
      " [ 2.3  9.  10.   9.   8.1]]\n",
      "9\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[ 3.5  3.9  4.3  4.8  5.3]\n",
      " [ 3.1  3.5  4.8  5.3  5.9]\n",
      " [ 2.8  2.5 10.   5.9  6.5]\n",
      " [ 2.5 10.  10.  10.   7.3]\n",
      " [ 2.3  9.  10.   9.   8.1]]\n",
      "10\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[ 3.5  3.9  4.3  4.8  5.3]\n",
      " [ 3.1  3.5  4.8  5.3  5.9]\n",
      " [ 2.8  2.5 10.   5.9  6.5]\n",
      " [ 2.5 10.  10.  10.   7.3]\n",
      " [ 2.3  9.  10.   9.   8.1]]\n",
      "11\n"
     ]
    }
   ],
   "execution_count": 5
  },
  {
   "cell_type": "code",
   "id": "54a22543-95cb-4e13-a760-624088217550",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-08-15T07:22:25.454550Z",
     "start_time": "2025-08-15T07:22:25.445280Z"
    }
   },
   "source": [
    "#求解贝尔曼方程,和上面代码没有区别\n",
    "gridworld.show()                     #打印gridworld\n",
    "gridworld.showPolicy(policy)         #打印策略\n",
    "print(\"random policy\")\n",
    "#policy evaluation\n",
    "value = np.zeros(rows*columns)\n",
    "value_pre = value.copy()+1\n",
    "\n",
    "cnt = 0\n",
    "while(np.sum((value_pre-value)**2)>0.001):\n",
    "    #policy evaluation\n",
    "    \n",
    "    value_pre = value.copy() #用来验证整个迭代是否收敛的\n",
    "\n",
    "    value0 = value.copy()+1  #这里是随机一个值，然后通过迭代的方式求解贝尔曼方程\n",
    "                             #这里写了固定，也可以随机，最终都会收敛到同一个结果\n",
    "    truncatedCnt = 10       # 1:迭代50次  2：迭代26次 3：迭代18次 4：迭代14次  10：迭代6次 100：迭代2次\n",
    "    while(np.sum((value0-value)**2)>0.001):\n",
    "        value0 = value.copy()\n",
    "        \n",
    "        truncatedCnt = truncatedCnt-1  #这里这里加个限制，其实就是truncated policy iteration了\n",
    "        if truncatedCnt<0:             #其实就是贝尔曼迭代次数\n",
    "            break\n",
    "                \n",
    "        for i in range(rows * columns):   #使用当前策略policy，计算每个state的value，进行迭代\n",
    "            j = policy[i]                 #不用遍历5个action了，直接百分百选择policy的策略\n",
    "            score, nextState = gridworld.getScore(i,j)   #返回得分以及下一步的state id\n",
    "            value[i] = score + value0[nextState] * gamma #贝尔曼迭代\n",
    "    \n",
    "    \n",
    "    for i in range(rows * columns):\n",
    "        for j in range(5): # 5个action\n",
    "            score,nextState = gridworld.getScore(i,j)     #获取Si状态中，执行动作j后的（得分，下一个状态）\n",
    "            qtable[i][j] = score + gamma * value[nextState]\n",
    "\n",
    "    #policy improvement\n",
    "    policy = np.argmax(qtable,axis=1)  #更新策略，非常无敌\n",
    "\n",
    "\n",
    "    \n",
    "    gridworld.showPolicy(policy)      #各种打印信息\n",
    "    print(value.reshape(rows,columns))\n",
    "    cnt = cnt+1\n",
    "    print(cnt)\n",
    "\n",
    "    "
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "⬜️⬜️⬜️⬜️⬜️\n",
      "⬜️🚫🚫⬜️⬜️\n",
      "⬜️⬜️🚫⬜️⬜️\n",
      "⬜️🚫✅🚫⬜️\n",
      "⬜️🚫⬜️⬜️⬜️\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "random policy\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[0.         0.38742049 0.8178877  1.2961846  1.8276256 ]\n",
      " [0.         0.         1.2961846  1.8276256  2.4181156 ]\n",
      " [0.         0.         6.5132156  2.4181156  3.0742156 ]\n",
      " [0.         6.5132156  6.5132156  6.5132156  3.8032156 ]\n",
      " [0.         5.5132156  6.5132156  5.5132156  4.6132156 ]]\n",
      "1\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[2.27101786 2.65843834 3.08890555 3.56720245 4.09864345]\n",
      " [1.92233941 2.27101786 3.56720245 4.09864345 4.68913345]\n",
      " [1.60852882 1.32609928 8.78423345 4.68913345 5.34523345]\n",
      " [1.32609928 8.78423345 8.78423345 8.78423345 6.07423345]\n",
      " [1.0719127  7.78423345 8.78423345 7.78423345 6.88423345]]\n",
      "2\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[3.06287282 3.45029331 3.88076052 4.35905742 4.89049842]\n",
      " [2.71419438 3.06287282 4.35905742 4.89049842 5.48098842]\n",
      " [2.40038378 2.11795425 9.57608842 5.48098842 6.13708842]\n",
      " [2.11795425 9.57608842 9.57608842 9.57608842 6.86608842]\n",
      " [1.86376766 8.57608842 9.57608842 8.57608842 7.67608842]]\n",
      "3\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[3.33897557 3.72639606 4.15686327 4.63516017 5.16660117]\n",
      " [2.99029713 3.33897557 4.63516017 5.16660117 5.75709117]\n",
      " [2.67648654 2.394057   9.85219117 5.75709117 6.41319117]\n",
      " [2.394057   9.85219117 9.85219117 9.85219117 7.14219117]\n",
      " [2.13987042 8.85219117 9.85219117 8.85219117 7.95219117]]\n",
      "4\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[3.43524665 3.82266714 4.25313435 4.73143125 5.26287225]\n",
      " [3.08656821 3.43524665 4.73143125 5.26287225 5.85336225]\n",
      " [2.77275761 2.49032808 9.94846225 5.85336225 6.50946225]\n",
      " [2.49032808 9.94846225 9.94846225 9.94846225 7.23846225]\n",
      " [2.23614149 8.94846225 9.94846225 8.94846225 8.04846225]]\n",
      "5\n",
      "➡️➡️➡️➡️⬇️\n",
      "⬆️⏫️⏩️➡️⬇️\n",
      "⬆️⬅️⏬➡️⬇️\n",
      "⬆️⏩️✅⏪⬇️\n",
      "⬆️⏩️⬆️⬅️⬅️\n",
      "[[3.44040042 3.82782091 4.25828812 4.73658502 5.26802602]\n",
      " [3.09172198 3.44040042 4.73658502 5.26802602 5.85851602]\n",
      " [2.77791139 2.49548185 9.95361602 5.85851602 6.51461602]\n",
      " [2.49548185 9.95361602 9.95361602 9.95361602 7.24361602]\n",
      " [2.24129527 8.95361602 9.95361602 8.95361602 8.05361602]]\n",
      "6\n"
     ]
    }
   ],
   "execution_count": 6
  },
  {
   "cell_type": "code",
   "id": "32a08872-b6b6-4b8a-b552-17ba1251e3f2",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-08-15T07:22:25.456943Z",
     "start_time": "2025-08-15T07:22:25.455556Z"
    }
   },
   "source": [],
   "outputs": [],
   "execution_count": 6
  },
  {
   "cell_type": "code",
   "id": "2326c4f5-b27d-4f32-860c-e953f50dc985",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-08-15T07:22:25.459061Z",
     "start_time": "2025-08-15T07:22:25.456943Z"
    }
   },
   "source": [],
   "outputs": [],
   "execution_count": 6
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
